package com.example.springboottest.example.sort;

/**
 * 简单选择排序，时间复杂度 O(n²)
 * 实质和交换排序相同，但多了个临时下标变量min，大大减少了数据的交换次数
 * 每次循环只用把最小的数字找到，交换一次！！！
 * 效率略优于冒泡排序
 */
public class SimpleSelectionSort extends SortBase {
    public static void main(String[] args) {
        SimpleSelectionSort sort = new SimpleSelectionSort();
        sort.sort(sort.dataArr);
        sort.show(sort.dataArr);
    }

    @Override
    public void sort(int[] dataArr) {
        int swapCount = 0;
        int min = 0;
        for (int i = 0; i < dataArr.length; i++) {
            min = i;
            show(dataArr);
            for (int j = i + 1; j < dataArr.length; j++) {
                if (dataArr[min] > dataArr[j])
                    min = j;
            }
            if (min != i) {
                swapCount++;
                swap(dataArr, i, min);
            }
        }
        System.out.println("简单选择排序完成，共进行\t" + swapCount + "次交换");
    }
}
